{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Number of Ways to Place Houses"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countHousePlacements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计放置房子的方式数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一条街道上共有 <code>n * 2</code> 个 <strong>地块</strong> ，街道的两侧各有 <code>n</code> 个地块。每一边的地块都按从 <code>1</code> 到 <code>n</code> 编号。每个地块上都可以放置一所房子。</p>\n",
    "\n",
    "<p>现要求街道同一侧不能存在两所房子相邻的情况，请你计算并返回放置房屋的方式数目。由于答案可能很大，需要对 <code>10<sup>9</sup> + 7</code> 取余后再返回。</p>\n",
    "\n",
    "<p>注意，如果一所房子放置在这条街某一侧上的第 <code>i</code> 个地块，不影响在另一侧的第 <code>i</code> 个地块放置房子。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 1\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>\n",
    "可能的放置方式：\n",
    "1. 所有地块都不放置房子。\n",
    "2. 一所房子放在街道的某一侧。\n",
    "3. 一所房子放在街道的另一侧。\n",
    "4. 放置两所房子，街道两侧各放置一所。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/05/12/arrangements.png\" style=\"width: 500px; height: 500px;\">\n",
    "<pre><strong>输入：</strong>n = 2\n",
    "<strong>输出：</strong>9\n",
    "<strong>解释：</strong>如上图所示，共有 9 种可能的放置方式。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-number-of-ways-to-place-houses](https://leetcode.cn/problems/count-number-of-ways-to-place-houses/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-number-of-ways-to-place-houses](https://leetcode.cn/problems/count-number-of-ways-to-place-houses/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1', '2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHousePlacements(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        a, b = 0, 1\n",
    "        for i in range(n):\n",
    "            a, b = b, a+b\n",
    "        return (a+b)**2 % MOD\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHousePlacements(self, n: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        if n==1: return 4\n",
    "        if n==2: return 9\n",
    "        dp = [0]*n\n",
    "        dp[0],dp[1] = 2,3\n",
    "        for i in range(2,n):\n",
    "            dp[i] = dp[i-1] + dp[i-2]\n",
    "        return dp[-1]*dp[-1]%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 一侧不影响另一侧，独立排列，ret ** 2\n",
    "# 排列方式 2 ** n - (不合法)\n",
    "# 1: 只能选0\n",
    "# 0：可以选0 或 1\n",
    "class Solution:\n",
    "    def countHousePlacements(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i, flag):\n",
    "            if i == n-1:\n",
    "                return 1\n",
    "            ret = 0\n",
    "            if not flag:\n",
    "                ret += dfs(i+1, 0) + dfs(i+1, 1)\n",
    "            else:\n",
    "                ret += dfs(i+1, 0)\n",
    "            return ret \n",
    "        ret = dfs(0, 0) + dfs(0, 1)\n",
    "        return ret ** 2 % (10 ** 9 + 7)\n",
    "\n",
    "class Solution:\n",
    "    def countHousePlacements(self, n: int) -> int:\n",
    "        dp = [[0] * 2 for _ in range(n+1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, n+1):\n",
    "            dp[i][0] = dp[i-1][0] + dp[i-1][1]\n",
    "            dp[i][1] = dp[i-1][0]\n",
    "        return (dp[-1][0] + dp[-1][-1]) ** 2 % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHousePlacements(self, n: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        dp = [[0] * 2 for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i][0] += dp[i - 1][0] + dp[i - 1][1]\n",
    "            dp[i][1] += dp[i - 1][0]\n",
    "        tot = sum(dp[-1])\n",
    "        return tot * tot % mod\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHousePlacements(self, n: int) -> int:\n",
    "\n",
    "        MOD = 10**9+7\n",
    "\n",
    "        def dp(x, cache):\n",
    "            if x in cache:\n",
    "                return cache[x]\n",
    "            if x == 0:\n",
    "                cache[x] = 1\n",
    "                return 1\n",
    "            if x == 1:\n",
    "                cache[x] = 2\n",
    "                return 2\n",
    "            a = int(dp(x-1, cache)%MOD)\n",
    "            b = int(dp(x-2, cache)%MOD)\n",
    "            res = int((a + b)%MOD)\n",
    "            cache[x] = res\n",
    "            return res\n",
    "\n",
    "        return int((dp(n, {}) ** 2)%MOD)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "@cache\n",
    "def fun(i, status):\n",
    "    if i == 0 and status == False: return 1\n",
    "    if i == 0 and status == True: return 0\n",
    "    if i == 1 and status == True: return 1\n",
    "    if i == 1 and status == False: return 1\n",
    "\n",
    "    if status == True:\n",
    "        return fun(i - 1, False)\n",
    "    return fun(i - 1, True) + fun(i - 1, False)\n",
    "    \n",
    "\n",
    "class Solution:\n",
    "    def countHousePlacements(self, n: int) -> int:\n",
    "        return ((fun(n,True) + fun(n, False) ) ** 2) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "class Solution:\n",
    "    def countHousePlacements(self, n: int) -> int:\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, a, b):\n",
    "            if idx == n:\n",
    "                return 1\n",
    "            res = 0\n",
    "            t1 = [0] if a == 1 else [0, 1]\n",
    "            t2 = [0] if b == 1 else [0, 1]\n",
    "            for x in t1:\n",
    "                for y in t2:\n",
    "                    res += dfs(idx + 1, x, y)\n",
    "                    res %= kmod\n",
    "            return res\n",
    "\n",
    "        ans = dfs(0, 0, 0)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHousePlacements(self, n: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        dp = [[0] * 3 for _ in range(n)]\n",
    "        dp[0][0], dp[0][1], dp[0][2] = 1, 2, 1\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = sum(dp[i - 1])\n",
    "            dp[i][1] = dp[i - 1][0] * 2 + dp[i - 1][1]\n",
    "            dp[i][2] = dp[i - 1][0]\n",
    "        return sum(dp[-1]) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countHousePlacements(self, n: int) -> int:\n",
    "        return pow(self.get_low(n), 2) % (10 ** 9 + 7)\n",
    "\n",
    "    @lru_cache(maxsize=10000)\n",
    "    def get_low(self, n):\n",
    "        if n == 1:\n",
    "            return 2\n",
    "        if n == 2:\n",
    "            return 3\n",
    "        return self.get_low(n - 1) + self.get_low(n - 2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHousePlacements(self, n: int) -> int:\n",
    "        P=10**9+7\n",
    "        @lru_cache(None)\n",
    "        def f(v1,v2,i):\n",
    "            z=0\n",
    "            a1=[0] if v1==1 else [0,1]\n",
    "            a2=[0] if v2==1 else [0,1]\n",
    "            for x in a1:\n",
    "                for y in a2:\n",
    "                    z+=(1 if i==n-1 else f(x,y,i+1))\n",
    "            return z%P\n",
    "        return f(0,0,0)%P"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHousePlacements(self, n: int) -> int:\n",
    "        dp = [[1,1,1,1] for _ in range(n)]\n",
    "        for i in range(1,n):\n",
    "            dp[i][0] = dp[i-1][0] + dp[i-1][3] + dp[i-1][2] + dp[i-1][1] \n",
    "            dp[i][1] = dp[i-1][0] + dp[i-1][2] \n",
    "            dp[i][2] = dp[i-1][0] + dp[i-1][1] \n",
    "            dp[i][3] = dp[i-1][0] \n",
    "        return sum(dp[n-1]) %(10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHousePlacements(self, n: int) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param n:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        dp = {}\n",
    "        dp[(1, 0)] = 1\n",
    "        dp[(1, 1)] = 1\n",
    "        dp[(1, 2)] = 1\n",
    "        dp[(1, 3)] = 1\n",
    "        mod1 = 10 ** 9 + 7\n",
    "        for i in range(2, n + 1):\n",
    "            dp[(i, 0)] = dp[(i - 1, 0)] + dp[(i - 1, 1)] + dp[(i - 1, 2)] + dp[(i - 1, 3)]\n",
    "            dp[(i, 1)] = dp[(i - 1, 0)] + dp[(i - 1, 2)]\n",
    "            dp[(i, 2)] = dp[(i - 1, 0)] + dp[(i - 1, 1)]\n",
    "            dp[(i, 3)] = dp[(i - 1, 0)]\n",
    "\n",
    "        cnt = 0\n",
    "        for i in range(0, 4):\n",
    "            cnt += dp[(n, i)]   % mod1\n",
    "\n",
    "        mod1 = 10 ** 9 + 7\n",
    "        return cnt % mod1\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.countHousePlacements(2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHousePlacements(self, n: int) -> int:\n",
    "        m = 10 ** 9 + 7\n",
    "\n",
    "        @cache\n",
    "        def f(i):\n",
    "            return 1 if i < 1 else (f(i - 2) + f(i - 1)) % m\n",
    "        \n",
    "        return pow(f(n), 2, m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHousePlacements(self, n: int) -> int:\n",
    "        if n==1 :\n",
    "            return 4\n",
    "        elif n==2:\n",
    "            return 9\n",
    "        else:\n",
    "            a = [ 1,4]\n",
    "            b = [1,2 ]\n",
    "            c = [1,2]\n",
    "            d = [1,1]\n",
    "            for j in range( 3,n+1 ):\n",
    "                aj =  a[-1] + b[-1] + c[-1] + d[-1]\n",
    "                bj = a[-1] + c[-1]\n",
    "                cj = a[-1] + b[-1 ]\n",
    "                dj =  a[-2] + b[-2] + c[-2] + d[-2]\n",
    "                a.append( aj )\n",
    "                b.append( bj )\n",
    "                c.append( cj )\n",
    "                d.append( dj )\n",
    "            return ( a[-1] + b[-1] + c[-1] + d[-1] )%( 10**9 + 7 )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHousePlacements(self, n: int) -> int:\n",
    "      # 方案数有重合\n",
    "      f = [[0] * 4 for _ in range(n)]\n",
    "      f[0] = [1, 1, 1, 1]\n",
    "\n",
    "      for i in range(1, n):\n",
    "        f[i][0] = f[i-1][0] + f[i-1][1] + f[i-1][2] + f[i-1][3]\n",
    "        f[i][1] = f[i-1][0] + f[i-1][2]\n",
    "        f[i][2] = f[i-1][0] + f[i-1][1]\n",
    "        f[i][3] = 1 if i == 1 else sum(f[i-2])\n",
    "\n",
    "      return sum(f[-1]) % (10 ** 9 + 7)\n",
    "\n",
    "      # if n == 1: return 4\n",
    "      # f = [1, 2]\n",
    "      # for i in range(n-1):\n",
    "      #   f.append(f[-1] + f[-2])\n",
    "      # return f[-1] * f[-1] % (10 ** 9 + 7)\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHousePlacements(self, n: int) -> int:\n",
    "        @cache\n",
    "        def helper(n):\n",
    "            if n == 1:\n",
    "                return [1, 1]\n",
    "            have, notHave = helper(n-1)\n",
    "            return [notHave, have + notHave]\n",
    "        \n",
    "        return (sum(helper(n)) ** 2) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHousePlacements(self, n: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        @cache\n",
    "        def dfs(idx, last_two):\n",
    "            if idx == n*2:\n",
    "                return 1\n",
    "            ans = 0\n",
    "            ans += dfs(idx+1, (last_two[-1],last_two[0]^1))\n",
    "            if last_two[0] == 0:\n",
    "                ans += dfs(idx+1, (last_two[-1],last_two[0]))\n",
    "            return ans%MOD\n",
    "        return dfs(0,(0,0))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHousePlacements(self, n: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        @cache\n",
    "        def dfs(idx, last_two):\n",
    "            if idx == n*2:\n",
    "                return 1\n",
    "            ans = 0\n",
    "            for k in range(2):\n",
    "                if k == last_two[0] == 1:\n",
    "                    continue\n",
    "                ans += dfs(idx+1, (last_two[-1],k))\n",
    "            return ans%MOD\n",
    "        return dfs(0,(0,0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict\n",
    "import random\n",
    "import copy\n",
    "import sys\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countHousePlacements(self, n: int) -> int:\n",
    "\n",
    "        @lru_cache(typed=False, maxsize=128000000)\n",
    "        def dp(ii):\n",
    "            if ii == 0:\n",
    "                return 2\n",
    "\n",
    "            if ii == 1:\n",
    "                return 3\n",
    "\n",
    "            return (dp(ii-2) + dp(ii-1)) % MOD\n",
    "\n",
    "        val = dp(n-1)\n",
    "        return (val * val) % MOD\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def countHousePlacements(self, n: int) -> int:\n",
    "        # MOD = 10 ** 9 + 7\n",
    "        # @lru_cache(maxsize =None)\n",
    "        # def fib(x):\n",
    "        #     if x == 1:\n",
    "        #         return 2\n",
    "        #     if x == 2:\n",
    "        #         return 3\n",
    "        #     return fib(x - 1)%MOD + fib(x - 2)%MOD\n",
    "        # return fib(n)**2 %MOD\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "        visited = {}\n",
    "\n",
    "        def dfs(x):\n",
    "            if x == 1:\n",
    "                return 2\n",
    "            if x == 2:\n",
    "                return 3\n",
    "            if x in visited:\n",
    "                return visited[x]\n",
    "            res = dfs(x-1)%MOD  + dfs(x-2)%MOD \n",
    "            visited[x] = res\n",
    "            return res\n",
    "        ans = dfs(n)**2%MOD\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHousePlacements(self, n: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        @cache\n",
    "        def f(indx):\n",
    "            if indx >= n-1:\n",
    "                return n-indx+1\n",
    "            return (f(indx+1)+f(indx+2))%mod\n",
    "        return f(0)*f(0)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHousePlacements(self, n: int) -> int:\n",
    "        key = 10**9 + 7\n",
    "        @cache\n",
    "        def allocation(slots):\n",
    "            if slots == 0:\n",
    "                return 0, 1\n",
    "            \n",
    "            x, y = allocation(slots - 1)\n",
    "            return y, (x + y) % key\n",
    "            \n",
    "        x, y = allocation(n)\n",
    "        z = (x + y) % key\n",
    "        return (z * z) % key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countHousePlacements(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def f(i: int) -> int:\n",
    "            if i == n:\n",
    "                return 1\n",
    "            elif i == n - 1:\n",
    "                return 2\n",
    "            else:\n",
    "                return f(i + 2) + f(i + 1)\n",
    "\n",
    "        for i in reversed(range(n)):\n",
    "            f(i)\n",
    "\n",
    "        return f(0) * f(0) % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHousePlacements(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i <=0:\n",
    "                return 1\n",
    "            \n",
    "            return dfs(i-2) + dfs(i-1)\n",
    "        return dfs(n)**2 % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHousePlacements(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def fab(n):\n",
    "            if n == 1:\n",
    "                return 2\n",
    "            if n == 2:\n",
    "                return 3\n",
    "            return fab(n - 2) + fab(n - 1)\n",
    "\n",
    "        ans = fab(n) % 1000000007\n",
    "        return (ans * ans) % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 1000000007\n",
    "class Solution:\n",
    "    def countHousePlacements(self, n: int) -> int:\n",
    "        table = {}\n",
    "        def dp(last: int, i: int) -> int:\n",
    "            if (last, i) in table:\n",
    "                return table[last, i]\n",
    "            if i == n:\n",
    "                ans = 1\n",
    "            else:\n",
    "                ans = dp(0, i + 1)\n",
    "                if not last:\n",
    "                    ans = (ans + dp(1, i + 1)) % MOD\n",
    "            table[last, i] = ans\n",
    "            return ans\n",
    "        \n",
    "        ans = dp(0, 0)\n",
    "        return (ans * ans) % MOD\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHousePlacements(self, n: int) -> int:\n",
    "        mod=10**9+7\n",
    "        @cache\n",
    "        def dp(i,t):\n",
    "            if i==0:\n",
    "                return 1\n",
    "            if t==1:\n",
    "                return dp(i-1,0)\n",
    "            if t==0:\n",
    "                return dp(i-1,1)%mod+dp(i-1,0)%mod\n",
    "        return pow(dp(n-1,1)+dp(n-1,0),2,mod)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHousePlacements(self, n: int) -> int:\n",
    "        def fib(m):\n",
    "            record={1:2,2:3,3:5}\n",
    "            def f(x):\n",
    "                if x in record.keys():\n",
    "                    return record[x]\n",
    "                if x-1 not in record.keys():\n",
    "                    record[x-1]=f(x-1)\n",
    "                if x-2 not in record.keys():\n",
    "                    record[x-2]=f(x-2)\n",
    "                ans=record[x-1]+record[x-2]\n",
    "                record[x]=ans\n",
    "                return ans\n",
    "            return f(m)\n",
    "        return int(fib(n)**2)%int(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHousePlacements(self, n: int) -> int:\n",
    "        dic = {}\n",
    "        mod = 10**9+7\n",
    "        def do(i,j):\n",
    "            if i==1:\n",
    "                return 1\n",
    "            if i==2:\n",
    "                if j==True:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 2\n",
    "            if (i,j) in dic:\n",
    "                return dic[(i,j)]\n",
    "            \n",
    "            res = -1\n",
    "            if j==True:\n",
    "                res = do(i-1,False)\n",
    "            else:\n",
    "                res = do(i-1,False)+do(i-1,True)\n",
    "            dic[(i,j)] = res%mod\n",
    "            return res%mod\n",
    "        return ((do(n,True)+do(n,False))**2)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHousePlacements(self, n: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        @cache\n",
    "        def dfs(i,s):\n",
    "            if i == 0:\n",
    "                return 1\n",
    "            if(s):\n",
    "                return dfs(i-1,False)%mod\n",
    "            else:\n",
    "                return (dfs(i-1,False)+dfs(i-1,True))%mod\n",
    "        \n",
    "        return (dfs(n,False)*dfs(n,False))%mod\n",
    "            \n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
